/**
 * Created by L.jp
 * Description:一个机器人在m×n大小的地图的左上角（起点）。
 * 机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。
 * 可以有多少种不同的路径从起点走到终点？
 * User: 86189
 * Date: 2022-08-27
 * Time: 23:14
 */
public class Solution {
    public int uniquePaths (int m, int n) {
/*        //递归
        if(n==1 || m==1){
            return 1;
        }
        return uniquePaths(n-1,m)+uniquePaths(n,m-1);*/
        //表示到坐标n,m位置有多少数目
        int[][] dp=new int[n+1][m+1];
        //构造数组
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                //只能向下或者向上，那么数组第一行第一列都是1
                if(i==1){
                    dp[i][j]=1;
                    continue;
                }
                if (j==1){
                    dp[i][j]=1;
                    continue;
                }
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[n][m];
    }
}
